#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "Queue.h"

//二叉链表
typedef char BinaryTreeDataType;
typedef struct BinaryTreeNode
{
	BinaryTreeDataType val;
	struct BinaryTreeNode* _left;//指向左孩子
	struct BinaryTreeNode* _right;//指向右孩子
}BTNode;

////三叉链表
//typedef struct BinaryTreeNode
//{
//	BinaryTreeDataType val;
//	struct BinaryTreeNode* _left;//指向左孩子
//	struct BinaryTreeNode* _right;//指向右孩子
//	struct BinaryTreeNode* _parent;//指向父亲
//}BTNode;

//树节点的创建
BTNode* BuyNode(int x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		perror("malloc");
		return NULL;
	}

	node->val = x;
	node->_left = NULL;
	node->_right = NULL;

	return node;
}


//二叉树的创建
//BTNode* CreateBinaryTree(char* arr, int* pi)
BTNode* CreateBinaryTree()
{
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);
	BTNode* node7 = BuyNode(7);

	node1->_left = node2;
	node1->_right = node4;
	node2->_left = node3;
	node4->_left = node5;
	node4->_right = node6;
	node2->_right = node7;

	return node1;

	////遇到"#"就是空格，直接返回NULL
	//if (arr[*pi] == '#')
	//{
	//	(*pi)++;
	//	return NULL;
	//}

	//BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	//if (node == NULL)
	//{
	//	perror("malloc");
	//	exit(-1);
	//}
	//node->val = arr[(*pi)++];
	//node->_left = CreateBinaryTree(arr, pi);
	//node->_right = CreateBinaryTree(arr, pi);

	//return node;
}

//二叉树的销毁
void BinaryTreeDestroy(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}

	BinaryTreeDestroy(root->_left);//先销毁左子树
	BinaryTreeDestroy(root->_right);//再销毁右子树

	free(root);//最后消除根
	root = NULL;
}

//前序遍历
void PreorderTraversal(BTNode* root)
{
	if (root == NULL)
	{
		//printf("N ");
		return;
	}

	//先访问根节点
	printf("%c ", root->val);

	//访问其左子树
	PreorderTraversal(root->_left);

	//访问其右子树
	PreorderTraversal(root->_right);
}

//中序遍历
void InorderTraversal(BTNode* root)
{
	if (root == NULL)
	{
		//printf("N ");
		return;
	}

	//访问其左子树
	InorderTraversal(root->_left);

	//先访问根节点
	printf("%c ", root->val);

	//访问其右子树
	InorderTraversal(root->_right);
}

//后序遍历
void PostorderTraversal(BTNode* root)
{
	if (root == NULL)
	{
		//printf("N ");
		return;
	}

	//访问其左子树
	PostorderTraversal(root->_left);

	//访问其右子树
	PostorderTraversal(root->_right);

	//先访问根节点
	printf("%c ", root->val);
}

//二叉树节点个数
int GetBinaryTreeSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}

	return GetBinaryTreeSize(root->_left) + 
		GetBinaryTreeSize(root->_right) + 1;
}

//二叉树叶子结点的个数
int GetBinaryTreeLeafSize(BTNode* root)
{
	if (root == NULL)
	{
		return 0;
	}

	if (root->_left == NULL && root->_right == NULL)
	{
		return 1;
	}

	return GetBinaryTreeLeafSize(root->_left) + 
		GetBinaryTreeLeafSize(root->_right);
}

// 二叉树第k层结点个数
int GetBinaryTreeLevelKSize(BTNode* root, int k)
{
	if (root == NULL)
	{
		return 0;
	}
	if (k == 1)
	{
		return 1;
	}

	return GetBinaryTreeLevelKSize(root->_left, k - 1) + 
		GetBinaryTreeLevelKSize(root->_right, k - 1);
}

//二叉树查找值为x的节点
BTNode* BinaryTreeFind(BTNode* root, BinaryTreeDataType x)
{
	if (root == NULL)
	{
		return NULL;
	}

	//先跟根比较，相等直接返回根节点，不相等在于根的左右子树比较
	if (root->val == x)
	{
		return root;
	}

	//如果根的左子树的根与x相等，就直接返回，不必在比较右子树了。
	BTNode* ret1 = BinaryTreeFind(root->_left, x);
	if (ret1)
	{
		return ret1;
	}
	BTNode* ret2 = BinaryTreeFind(root->_right, x);
	if (ret2)
	{
		return ret2;
	}

	//走到这里说明，左右子树都不和x相等，所以返回NULL
	return NULL;
}

//二叉树的高度
int GetBinaryTreeDepth(BTNode* root)
{
	//如果根为空，说明该树的高度为0
	if (root == NULL)
	{
		return 0;
	}

	if (root->_left == NULL && root->_right == NULL)
	{
		return 1;
	}

	//树的高度等于左右子树中高的+1
	int height1 = GetBinaryTreeDepth(root->_left);
	int height2 = GetBinaryTreeDepth(root->_right);

	return height1 > height2 ? height1 + 1 : height2 + 1;
}

//二叉树的层序遍历
void LevelOrderTraversal(BTNode* root)
{
	if (root == NULL)
	{
		return;
	}

	//先创建队列
	Queue q = { 0 };
	QueueInit(&q);

	//先将根节点插入到队列中
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		//取出队头数据
		BTNode* front = GetQueueFront(&q);
		QueuePop(&q);

		printf("%d ", front->val);

		if (front->_left != NULL)
		{
			QueuePush(&q, front->_left);
		}
		if (front->_right != NULL)
		{
			QueuePush(&q, front->_right);
		}
	}

	QueueDestroy(&q);
}

//判断一个树是不是完全二叉树
bool BinaryTreeComplete(BTNode* root)
{
	if (root == NULL)
	{
		return false;
	}

	//先创建队列
	Queue q = { 0 };
	QueueInit(&q);

	//先将根节点插入到队列中
	QueuePush(&q, root);
	while (!QueueEmpty(&q))
	{
		//取出队头数据
		BTNode* front = GetQueueFront(&q);
		QueuePop(&q);

		//判断取到没有第一个空节点
		if (front == NULL)
		{
			//取到第一个空节点之后，判断队列中是不是全都是空
			while (!QueueEmpty(&q))
			{
				if (GetQueueFront(&q))
				{
					return false;
				}

				QueuePop(&q);
			}
			//到了这里说明队列里全是空节点
			break;
		}

		QueuePush(&q, front->_left);
		QueuePush(&q, front->_right);
	}

	QueueDestroy(&q);

	return true;
}

int main()
{
	//char arr[100] = "abc##de#g##f###";
	//int i = 0;

	BTNode* root = CreateBinaryTree();
	//BTNode* root = CreateBinaryTree(arr,&i);
	LevelOrderTraversal(root);
	printf("\n");
	//printf("PreorderTraversal：");
	//PreorderTraversal(root);
	//printf("\n");
	if (BinaryTreeComplete(root))
	{
		printf("yes\n");
	}
	else
	{
		printf("no\n");
	}
	//printf("InorderTraversal：");
	//InorderTraversal(root);
	//printf("\n");

	//printf("PostorderTraversal：");
	//PostorderTraversal(root);
	//printf("\n");


	//printf("BinaryTreeSzie：%d\n", GetBinaryTreeSize(root));

	//printf("GetBinaryTreeLeafSize：%d\n", GetBinaryTreeLeafSize(root));

	//printf("GetBinaryTreeLevel %d Size：%d\n",2,GetBinaryTreeLevelKSize(root, 2));

	//BTNode* ret = BinaryTreeFind(root, 10);
	//if (!ret)
	//{
	//	printf("找不到该节点\n");
	//}
	//else
	//{
	//	printf("BinaryTreeFind_10：%d\n", ret->val);

	//}

	//printf("GetBinaryTreeDepth：%d\n", GetBinaryTreeDepth(root));
	return 0;
}